學習資源

https://labuladong.online/algo/data-structure-basic/trie-map-basic/

學習記錄

今天是學習的第 29 天，主要學習了 Trie / 字典樹 / 前綴樹原理：

什麼是 Trie 樹？

Trie 樹（也叫做字典樹、前綴樹）是多叉樹結構的延伸，是一種針對字串進行特殊優化的資料結構。

這邊用程式碼舉個例子：

// 建立一棵字典樹
let trie = Trie.create();

// 向字典樹添加多個字串元素
trie.add("that");
trie.add("the");
trie.add("their");
trie.add("apple");
trie.add("them");

最終的字典樹長的就會如下圖，可以看到它沿用了部分重複的節點（如 t、h、e）以節省空間：

Trie 樹主要的應用場景

Trie 樹是一種針對字串特殊優化的資料結構，它對字串的處理有若干優勢：

一、節省儲存空間

這邊以 HashMap 來對比：在傳統的哈希表中，如果我們要儲存 "apple"、"app"、"appl" 這三個字串作為鍵，哈希表會將每個完整的字串都儲存一次。

回想哈希表的實現原理，鍵值對 key-value 會被儲存到 table 陣列中，也就是說它實際創建了三個完整的字串物件，總共佔用了 12 個字符的記憶體空間（apple 5個 + app 3個 + appl 4個）。

相對地，如果使用 Trie 樹來儲存這三個鍵，Trie 樹底層並不會重複儲存公共前綴。它會將相同的前綴部分共享，所以只需要 "apple" 這 5 個字符的記憶體空間就能儲存這三個鍵，大幅節省了儲存空間。

二、方便操作公共前綴

Trie 樹提供了許多方便的前綴操作功能。假設我們在 Trie 樹中儲存了 "that"、"the"、"them"、"apple" 這些鍵，我們可以：

• 找出給定字串的最短前綴：例如 "themxyz" 的最短前綴是 "the"
• 找出給定字串的最長前綴：例如 "themxyz" 的最長前綴是 "them"
• 檢查是否存在某個前綴：例如檢查 "tha" 會返回 true（因為有 "that"），但檢查 "thz" 會返回 false
• 找出所有以某個前綴開頭的鍵：例如以 "th" 為前綴的鍵有 "that"、"the"、"them"

這些前綴操作的時間複雜度都是 O(L)，其中 L 是前綴字串的長度。唯一的例外是查找所有符合某前綴的鍵，這個操作的複雜度取決於返回結果的數量。

三、可以使用通配符

Trie 樹支持通配符匹配，可以使用 . 符號來匹配任意單個字符。

這個特性讓我們能夠進行模糊搜尋，例如在存儲了 "that"、"the"、"team"、"zip" 等鍵的 Trie 樹中，我們可以用 "t.a." 這個模式來找出所有符合「t 開頭、第三個字符是 a、總共四個字符」的鍵，會找到 "team" 和 "that"。同樣地，用 ".ip" 可以匹配到 "zip"，因為它符合「任意字符 + ip」的模式。

四、可以按照字典序遍歷鍵

Trie 樹的結構天然支持按照字典序（alphabetical order）來遍歷所有的鍵。

這是因為 Trie 樹在儲存字符時，會按照字符的編碼順序來組織子節點，所以當我們遍歷整棵樹時，自然就會按照字典序輸出所有的鍵。

例如，一個包含 "that"、"the"、"them"、"zip"、"apple" 的 Trie 樹，遍歷時會依序得到 "apple"、"that"、"the"、"them"、"zip"。

Trie 樹的基本結構

Trie 樹本質上就是一棵從二叉樹衍生出來的多叉樹。

讓我們從熟悉的樹結構開始理解：

• 二叉樹節點：每個節點包含一個值 val，以及指向左右子節點的指針 left 和 right

// 基本的二叉樹節點
var TreeNode = function() {
    var val;
    var left;
    var right;
};

• 多叉樹節點：每個節點包含一個值 val，以及一個 children 陣列來儲存多個子節點的指針

// 基本的多叉樹節點
var TreeNode = function() {
    this.val = 0;
    this.children = [];
};

而 Trie 樹節點的結構則有其特殊之處：每個節點包含 val 欄位（儲存鍵對應的值）和一個固定大小的 children 陣列（通常是 256，對應 ASCII 字符集）。

// Trie 樹節點實現
var TrieNode = function() {
    this.val = null;
    this.children = new Array(256);
};

Trie 樹節點最關鍵的特性是：children 陣列的索引具有特殊意義，它代表一個字符。

例如 children[97] 如果非空，就表示這裡儲存了字符 'a'（因為 'a' 的 ASCII 碼是 97）。

這個陣列大小可以根據實際需求調整：

• 如果只處理小寫字母 a-z，可以設為 26
• 也可以用哈希表 HashMap<Character, TrieNode> 來替代陣列，效果相同

理解 Trie 樹結構的關鍵：

• 雖然一個節點理論上有 256 個子節點指針，但大多數時候都是空的
• 節點本身不儲存字符，字符是透過「子節點在父節點 children 陣列中的索引位置」來確定的
• 形象地說：Trie 樹用「樹枝」儲存字符（鍵），用「節點」儲存對應的資料（值）

在 Trie 樹的視覺化表示中：

• 從根節點到某個節點的路徑上，每條邊代表一個字符，連起來就形成一個字串
• 有些節點會標記為「結束節點」（儲存值），表示從根節點到這裡的路徑構成一個完整的鍵
• 沒有儲存值的節點只是路徑中的過渡節點

學習總結

• Trie 樹的定義：Trie 樹（字典樹 / 前綴樹）是一種多叉樹結構，專門針對字串處理進行優化的資料結構
• 節省空間：透過共享相同前綴的方式，避免重複儲存相同的字符，相比哈希表能節省大量記憶體空間
• 前綴操作優勢：能快速執行前綴相關操作，如查找最長 / 最短前綴、搜尋特定前綴的所有鍵，時間複雜度為 O(L)（L 為前綴長度）
• 支援通配符匹配：可使用 . 作為萬用字元進行模糊搜尋，方便進行模式匹配
• 字典序遍歷：Trie 樹的結構天然支援按字典順序遍歷所有鍵
• 節點結構特性：每個節點有固定大小的 children 陣列（通常 256 個），陣列索引代表字符的 ASCII 碼
• 字符儲存方式：字符不儲存在節點中，而是透過子節點在父節點 children 陣列的索引位置來確定